package com.eloancn.leecode.classic.backtrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * 打印（a,b,c） 中的所有可能的队列
 * 打印全排列，但是不能出现重复的数字
 *
 */
public class Backtracking {
    char[] chars ;
    List<String> res = new ArrayList<>();
    /**
     * 深度优先遍历
     */
    public void dfs(int count){
        if (count == chars.length -1) {
            res.add(new String(chars));
            return ;
        }
        HashSet set = new HashSet();
        // 判断set 里面是不是包含字符
        // 如果包含就需要剪枝
        for (int i=count;i<chars.length;i++) {

            if (set.contains(chars[i])){
                // 减枝
                continue;
            }
            set.add(chars[i]);
            swap(chars,i,count);
            dfs(count+1);
            swap(chars,i,count);
        }

    }
    private void swap(char []c,int i,int j){
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }


    public String[] permutation(String s) {
        chars = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    @Test
    public void runTest(){
        String[] abcs = permutation("abc");
        System.out.println(Arrays.toString(abcs));
    }
}
